package everyday;

import java.util.ArrayList;
import java.util.List;

public class T1073 {
    public int[] addNegabinary(int[] arr1, int[] arr2) {

        List<Integer> list =new ArrayList<Integer>();
        int i=arr1.length-1;
        int j=arr2.length-1;

        int carry=0;
        while(i>=0||j>=0||carry!=0){
            int x=carry;
            if (i>=0){
                x+=arr1[i];
                i--;
            }
            if(j>=0){
                x+=arr2[j];
                j--;
            }
            if (x>=2){
                list.add(x-2);
                carry=-1;
            }else if (x>=0){
                list.add(x);
                carry=0;
            }else{
                list.add(1);
                carry=1;
            }
        }
        int len=list.size();
        while (len>1&&list.get(len-1)==0){
            list.remove(len-1);
            len--;
        }
        int []res=new int[len];
        for (int k = 0; k <len ; k++) {
            res[k]=list.get(len-k-1);
        }
        return res;


    }
}
